L’insieme dei termini è definito dalle seguenti clausole:
una variabile è un termine;
un simbolo di costante è un termine;
un’espressione del tipo \(f ( t_{1} , \dots , t_{n} )\) è un termine, dove \(f\) è un simbolo di funzione \(n\)-ario e \(t_{1} , \dots , t_{n}\) sono termini.
Quel che si intende è che ogni stringa finita di simboli ottenuta applicando (un numero finito di volte) queste clausole è un termine. Formalmente, bisogna dare la seguente definizione ricorsiva.
Termini Dato un linguaggio \(L = Const \cup Fun \cup Rel\), consideriamo l’insieme \[\mathcal{S} = \Bigl ( \left \{ {(} , {)} \right \} \cup Vbl \cup Const \cup Func \Bigr )^*\] di tutte le stringhe di parentesi, variabili, simboli di costante e di funzione, e definiamo per ricorsione gli insiemi \(Term_{n}\) (per \(n \in \mathbb{N}\)) come segue: \[ Term_{0} = Vbl \cup Const \] \[ Term_{n + 1} = Term_{n} \cup \{f ( t_{1} \dots t_{k} ) \boldsymbol \mid f \in Fun \text{ e } t_{1} , \dots , t_{k} \in Term_{n} \text{ e } k = ar ( f ) \} \] L’insieme dei termini del linguaggio \(L\) (o, più brevemente, \(L\)-termini) è \[Term = \bigcup_{n \in \mathbb{N}} Term_{n} .\] Se \(t\) è un termine, il più piccolo \(n \in \mathbb{N}\) tale che \(t \in Term_{n}\) si chiama altezza di \(t\) e si indica con \(ht(t)\).
Sia \(L = \{ f,g,c \}\) un linguaggio del prim’ordine con \(f\) simbolo di funzione binario, \(g\) simbolo di funzione unario e \(c\) simbolo di costante. Ciascuna delle seguenti stringhe è un \(L\)-termine:
| \( x \) | \( y \) | \( c \) | \( v_0 \) | \( \dotsc \) |
| \( g(x) \) | \( f(c, v_0) \) | \( f(c, c) \) | \( g(c) \) | \( \dotsc \) |
| \( g(f(c,v_0)) \) | \( f(x,g(x)) \) | \( f(g(x),g(x)) \) | \( g(g(x)) \) | \( \dotsc \) |
e così via. I termini nella prima riga hanno altezza \(0\), quelli nella seconda hanno altezza \(1\), quelli nella terza hanno altezza \(2\) e così via.
Attenzione! Le virgole non sono necessarie, e in effetti non fanno parte della lista di simboli da utilizzare. Tuttavia il loro utilizzo è comodo per favorire la suddivisione tra i vari termini a cui si sta “applicando” il simbolo di funzione, qualora questo abbia arietà \(> 1\).
Anche i termini possono essere analizzati mediante alberi sintattici, che in questo caso saranno alberi etichettati finiti, ma non necessariamente binari: il numero dei successori di un nodo dipenderà dall’arietà dei simboli di funzione utilizzati.
Algoritmo di costruzione dell’albero sintattico di un termine
La radice viene etichettata con il termine dato.
Se un nodo è etichettato con una costante o una variabile, non si aggiunge nessun successore e il nodo diventerà una foglia dell’albero.
Se un nodo è etichettato con un termine della forma \(f ( t_{1}, \dotsc, t_{n} )\) dove \(ar(f) = n\), allora si aggiungono \(n\) successori al nodo etichettandoli con \(t_{1}, \dotsc, t_{n}\), rispettivamente.
Come nel caso delle proposizioni, se un nodo contiene una stringa che non è delle forme precedenti, l’algoritmo termina immediatamente e possiamo concludere che la stringa iniziale non era un termine ben formato.
Sia \(L = \{ f,g.c \}\) con \(f\) simbolo di funzione ternario, \(g\) simbolo di funzione unario e \(c\) simbolo di costante. L’albero sintattico del termine \(f(g(x),f(c,g(c),x),y)\) è
Supponiamo che \(t\) sia un termine della forma \(f(t_{1}, \dotsc, t_{n})\): come si individuano i termini \(t_{1}, \dotsc, t_{n}\)?
Si scorre la stringa di simboli racchiusa dalle parentesi più esterne, ovvero tra la parentesi sinistra che segue \(f\) e la sua parentesi destra di chiusura.
Se il primo simbolo che si incontra è una variabile o una costante, allora si tratta già del termine \(t_{1}\).
Se il primo simbolo è un simbolo di funzione, ad esempio \(h\), allora deve essere seguito da una parentesi sinistra: si cerca la parentesi destra che la chiude (utilizzando il contatore di parentesi) e si ottiene che \(t_{1}\) è il termine che va da \(h\) fino a tale parentesi di chiusura.
Individuato \(t_{1}\), si procede scorrendo quel che rimane della lista per individuare \(t_{2}\), poi \(t_{3}\), e così via fino a \(t_{n}\).
L’algoritmo termina quando sono stati individuati tutti i termini \(t_{1}, \dotsc, t_{n}\), dove \(n\) è l’arietà di \(f\). Come sempre si intende che se un passo dell’algoritmo non si può eseguire, oppure se restano ancora elementi nella stringa dopo aver individuato \(t_{1}, \dotsc, t_{n}\) allora l’algoritmo termina immediatamente e la stringa analizzata non era un termine.
Sia \(L = \{ f,g,c \}\) con \(f\) simbolo di funzione ternario, \(g\) simbolo di funzione unario e \(c\) simbolo di costante, e sia \(t\) il termine della forma \(f(t_{1}, t_{2}, t_{3})\) dato da \[f(g(g(x)) c f(g(z) x g(c)))\]
Analogamente, si può vedere che il termine \(f(g(z)xg(c))\) è a sua volta della forma \(f(s_{1}, s_{2}, s_{3})\) dove \(s_{1}\) è \(g(z)\), \(s_{2}\) è \(x\) e \(s_{3}\) è \(g(c)\).
Reintroducendo le virgole di separazione, \(t\) è dunque il termine \[f(g(g(x)), c,f(g(z), x, g(c)))\]
Osservazione Questo mostra anche che si può fare a meno di utilizzare le virgole per separare i termini. Tuttavia noi continueremo ad utilizzarle perché spesso aiutano la lettura del termine stesso.
L’albero sintattico del termine
\(h ( f ( h ( x , z , g ( f( c ) , y ) ) ) , g ( x , f ( g ( z , y) ) ) , f ( h ( f (z) , h (y, c , x ) , z ) ) )\)
dove \(c\) è un simbolo di costante e \(f\), \(g\) e \(h\) sono simboli di funzione di arietà \(1\), \(2\) e \(3\), è
L’albero sintattico abbreviato dello stesso termine
\(h ( f ( h ( x , z , g ( f( c ) , y ) ) ) , g ( x , f ( g ( z , y) ) ) , f ( h ( f (z) , h (y, c , x ) , z ) ) )\)
dove \(c\) è un simbolo di costante e \(f\), \(g\) e \(h\) sono simboli di funzione di arietà \(1\), \(2\) e \(3\), è
Abbiamo due misure naturali di complessità per un termine \(t\):
\(lh ( t )\), la lunghezza (incluse le parentesi) della stringa \(t\) e
\(ht ( t )\), l’altezza di \(t\): quest’ultima coincide con l’altezza dell’albero sintattico di \(t\) diminuita di \(1\).
Quindi se \(t\) è il termine visto nella slide precedente
\[h ( f ( h ( x , z , g ( f( c ) , y ) ) ) , g ( x , f ( g ( z , y) ) ) , f ( h ( f (z) , h (y, c , x ) , z ) ) )\]
allora \(lh ( t ) = 48\) e \(ht ( t ) = 5\).
Siano \(f,g,h\) simboli di funzione con \(ar(f) = 1\), \(ar(g) = 2\) e \(ar(h)=3\), e \(a,b,c\) simboli di costante. Per ciascuno delle seguenti stringhe determinare se sono termini provando a costruirne l’albero sintattico. Nel caso siano termini determinarne l’altezza.
\(f(g(a,c))\)
\(h(f(x),g(f(a),y),z)\)
\(h(a,b,x)\)
\(g(h(x,x,x),f(x,x))\)
\(f(f(f(g(g(a,c),g(x,y)))))\)
\(h(f(a),g(f(a),a))\)
Consideriamo il linguaggio \(L = \{ +, \cdot , 1 \}\) dove \(+\) e \(\cdot\) sono simboli di funzione binari e \(1\) è un simbolo di costante. I termini di questo linguaggio sono del tipo
| \( x \) | \( y \) | \( 1 \) | \( z \) | \( \dotsc \) |
| \( +(x,1) \) | \(\cdot(x,x)\) | \(\dotsc\) | ||
| \(+(\cdot(x,x),1)\) | \(\cdot(+(1,1), \cdot(x,x))\) | \(\dotsc\) |
Consideriamo ora il termine \(t\) \[+ ( +( \cdot(x,x), \cdot(+(1,1),x)) ,1).\] Utilizzando la notazione infissa (ovvero scrivendo \(t + s\) anziché \(+(t,s)\) e \(t \cdot s\) anziché \(\cdot (t,s)\)) il termine \(t\) diventa \[(((x \cdot x) + ((1+1) \cdot x)) + 1),\] da cui omettendo le parentesi e utilizzando le solite convenzioni per la notazione sull’addizione e moltiplicazione si ottiene \[x^2 + 2x +1.\] In altre parole, il termine \(t\) “rappresenta” il polinomio \(x^2 + 2x +1\), una volta che i simboli \(+ , \cdot, 1\) vengano interpretati nella maniera usuale!
Più in generale, si può osservare che i termini in questo linguaggio \(L\) corrispondono esattamente ai polinomi a coefficienti interi non negativi (ovvero in cui tutti i coefficienti sono numeri naturali).
Consideriamo nuovamente il linguaggio \(L = \{ +, \cdot , 1 \}\) dove \(+\) e \(\cdot\) sono simboli di funzione binari e \(1\) è un simbolo di costante.
A quali polinomi corrispondono i seguenti termini?
\(+(+(+(x,x),y),\cdot(z,z))\)
\(+(+( \cdot(x,\cdot(x,x)) ,+(x,x)), +(+(1,1),1))\)
\(+( +(\cdot(+(1,1),x),x), +(1,1))\)
Scrivere termini del linguaggio \(L\) che rappresentino i seguenti polinomi:
\(x+y+3\)
\(x+y^2 + 3z\)
\(z^2 + 2x\)